1. Field of the Invention
In general, the present invention relates to an arithmetic decoding method. More particularly, the present invention relates to an arithmetic decoding apparatus for decoding data which has been encoded by adoption of the CABAC (Context-Adaptive Binary Arithmetic Coding) technique.
2. Description of the Related Art
The CABAC technique is one of entropy coding techniques in the H.264 which has been standardized by the ITU-T (International Telecommunication Union-Telecommunication standardization sector). In accordance with the CABAC technique, prior to an encoding process, various kinds of multi-value data is converted into binary data by expressing the multi-value data in terms of ‘0’ and ‘1’ symbols. Then, the binary data is encoded by carrying out a binary arithmetic coding process. In a decoding process, on the other hand, a process is carried out in an opposite manner.
The binary data expressed in terms of ‘0’ and ‘1’ symbols is subjected to the binary arithmetic encoding process which is a process to replace {0, 1} with {LPS, MPS}. The MPS is an abbreviation for the Most Probable Symbol which is a symbol inferred to have a high appearance probability. On the other hand, the LPS is an abbreviation for the Least Probable Symbol which is a symbol other than the MPS.
Then, the binary data expressed in terms of two different symbols, i.e., MPSes and LPSes, is encoded by making use of arithmetic codes. The MPS is determined to be ‘0’ or ‘1’ by prediction for each symbol on the basis of already processed data. That is to say, in an encoding process, the MPS value of a symbol to be encoded next is determined only from data which has been obtained as a result of a previous encoding process. In a decoding process, on the other hand, the MPS value of a symbol to be decoded next is determined only from data which has been obtained as a result of a previous decoding process.
In addition, a binary arithmetic encoding process includes a process of always sequentially switching the probability model (also referred to hereafter as a context) to a context properly selected from a plurality of contexts prepared in advance as a proper context proper for the present state. In the case of CABAC decoding processing, context variables each corresponding to one of the contexts are stored in advance in a context-variable table. A context proper for the present state is selected from the contexts prepared in advance by identifying a context variable denoted by notation context [ctxIdx] from the context variables, which have been stored in advance in the context-variable table, by making use of a context index denoted by notation ctxIdx pointing to the context variable. Each of the contexts is configured to include a probability state index pStateIdx showing an appearance probability and valMPS showing a most probable symbol (MPS) having a high appearance probability. The probability state index pStateIdx of a context shows an inferred value of the appearance probability of the LPS in the context in terms of a probability state in the predefined range 0 to 63. On the other hand, valMPS indicates that a symbol corresponding to the MPS is either 0 or 1. It is to be noted that, for every context variable, a probability state index pStateIdx of the context corresponding to the context variable is denoted by notation context [ctxIdx].pStateIdx whereas valMPS of the context corresponding to the context variable is denoted by notation context [ctxIdx].valMPS.
In a CABAC decoder, one context variable is selected to serve as a base of a Bin decoding process carried out to generate a piece of Bin data. In the following description, a piece of Bin data is also referred to as a Bin-data bit which is 1 bit of binary data. Then, an updated value of the context index used for identifying a context variable is calculated by making use of the Bin data generated as a result of the execution of a Bin decoding process. In the CABAC decoder, a decoding method is defined for each of parameters composing a macroblock. The parameter is referred to as an SE (syntax element). In CABAC decoding processing to produce Bin data for a syntax element, a plurality of context variables are used in order to generate a plurality of Bin-data bits. Then, for the Bin-data bits, multi-value data of the syntax element is found in accordance with a multi-value conversion method which is determined uniquely for the syntax element.
In a Bin decoding process of generating one Bin-data bit, in a number of cases, context indexes each determined in accordance with the value of the immediately preceding Bin-data bit as an index for identifying a context variable used in a Bin decoding process exist at the beginning of the syntax element and in the middle of the syntax element in an ascending order. In addition, in many cases, the length of the Bin data obtained as a result of a Bin decoding process to generate the Bin data for a syntax element is indeterminate till the immediately preceding Bin data is obtained as a result of a Bin decoding process. It is to be noted that the length of the Bin data is the number of Bin-data bits each obtained as a result of a Bin decoding process. Thus, in a Bin decoding process of generating Bin data for a syntax element after the end of a Bin decoding process of generating Bin data for another syntax element, each context index is not determined till a Bin decoding process of generating the immediately preceding Bin data for a syntax element is completed. In addition, in a Bin decoding process of generating Bin data for a syntax element, there are a case in which the same context variable identified by the same context index is used consecutively in different decoding processes for generating different Bin-data bits for the syntax element and a case in which different context variables identified by different context indexes are used in different decoding processes of generating different Bin-data bits for the syntax element.
There is a case in which the context index identifying a context variable for generating a Bin-data bit at the head of Bin data is a number determined in accordance with the syntax element obtained from the Bin data. However, there is also a case in which the context index identifying a context variable for a Bin-data bit at the head of Bit data is a number determined in accordance with a syntax element which is selected from approximately four candidates in accordance with what values are the values of a plurality of syntax elements each already obtained from Bin data generated in previous decoding processes. The context index identifying a context variable for a Bin-data bit other than the Bin-data bit at the head of the syntax element is computed in accordance with whether the immediately preceding Bin-data bit obtained as a result of a Bin decoding process carried out by execution of the immediately preceding Bin decoding instruction is 0 or 1. In addition, the CABAC decoder determines whether or not the end of a syntax element has been obtained as a result of CABAC decoding processing by referring to a variable-length code table defined for the syntax element.
The CABAC decoding procedure includes a number of branch processes each implemented by a branch instruction of a program implementing the CABAC decoding procedure. In addition, the context index used for identifying a context variable is not always incremented by one for every decoding process. For example, it is possible to provide a configuration in which the same context index for identifying a context variable is used successively in all the Bin decoding processes or the context index may be incremented by two for every Bin decoding process. At any rate, the context index is calculated in accordance with the value of the immediately preceding Bin-data bit obtained as a result of a Bin decoding process carried out by execution of the immediately preceding Bin decoding instruction as described above and the process of calculating the context index is not simple. In addition, the length of Bin data obtained as a result of CABAC decoding processing to generate the Bin data for a syntax element is not a fixed value determined by the syntax element. Instead, the length of Bin data obtained as a result of CABAC decoding processing to generate the Bin data for a syntax element varies in accordance with the decoding-process path which may or may not include branch processes as described above. Thus, the process carried out by the CABAC decoder to determine whether or not the end of a syntax element has been generated as a result of a Bin decoding process is also complicated as well.
There is a case in which the context index identifying a context variable for the Bin-data bit at the head of Bit data is a number determined uniquely in accordance with the syntax element which is obtained as an eventual result of CABAC decoding processing to generate Bit data for the syntax element. On the other hand, there is also a case in which the context index identifying a context variable for the Bin-data bit at the head of Bit data is a number determined uniquely from adjacent macroblocks which are each composed of syntax elements. If the context index identifying a context variable for the Bin-data bit at the head of Bit data is a number determined uniquely from adjacent macroblocks, syntax elements pertaining to the adjacent macroblock right above the present syntax element and syntax elements pertaining to the adjacent macroblock on the left side of the present syntax element are referenced. Image portions such as the upper edge of the image and the right and left edges of the image may not have adjacent macroblocks in some cases. In such cases, an exception process also needs to be carried out as well. As a result, the Bin decoding process becomes extremely complicated.
In order to carry out the CABAC decoding processing by making use of hardware, it is necessary to provide a dedicated memory to be used for storing 460 context variables and a dedicated memory to be used for holding preceding syntax elements to be used for computing a context index identifying a context variable for the Bin-data bit at the head of Bit data. In addition, it is also necessary to provide state machines according to individual decoding methods which each correspond to a syntax element. Thus, the CABAC decoder raises problems that extremely complex control needs to be executed and the circuit size undesirably becomes large.
On the other hand, it is also possible to carry out the CABAC decoding processing by making use of software executed on a hardware combination assumed to include the CPU and a coprocessor. When a coprocessor instruction for giving one context index is executed, a Bin decoding process is carried out in order to generate a Bin-data bit and it can be assumed that an instruction is executed in order to store the Bin-data bit in a register which is employed in the CPU. As an apparatus for executing such an instruction, there has been proposed a CABAC decoder which pipelines the Bin decoding processes to generate Bin data in order to be capable of operating at about the same high frequency as the CPU. For details of the proposed CABAC decoder, the reader is suggested to refer to Japanese Patent Laid-open No. 2007-074648 which includes a table shown in FIG. 6.